package com.ting.test.algorithms.滑动窗口;

import java.util.LinkedList;

/**
 * Created by 雷霆 on 2020/11/10.
 * <p>
 * Description：
 * 给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，必须满足：
 * sub中最大值 – sub中最小值 <= num，
 * 返回arr中达标子数组的数量给定一个整型数组arr，和一个整数num
 * 某个arr中的子数组sub，如果想达标，必须满足：
 * sub中最大值 – sub中最小值 <= num，
 * 返回arr中达标子数组的数量
 */
public class MinSubArr {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 4, 6, 7, 8, 9, 3};
        int num = 3;
        int result = test1(arr, 3);
        System.out.println(result);
    }

    private static int test1(int[] arr, int num) {
        if (null == arr || arr.length < 1 || num < 0) {
            return 0;
        }
        int result = 0;
        LinkedList<Integer> maxQueue = new LinkedList<>();
        LinkedList<Integer> minQueue = new LinkedList<>();
        int R = 0;
        for (int L = 0; L < arr.length; L++) {
//            R = 0;
            while (R < arr.length) {
                //最大值队列入队操作
                if (!maxQueue.isEmpty() && maxQueue.peekLast() <= arr[R]) {
                    maxQueue.pollLast();
                }
                maxQueue.addLast(R);

                //最小值队列入队操作
                if (!minQueue.isEmpty() && minQueue.peekLast() >= arr[R]) {
                    minQueue.pollLast();
                }
                minQueue.addLast(R);

                //判断是否仍然符合题意
                if (arr[maxQueue.peekLast()] - arr[minQueue.peekLast()] >= num) {
                    break;
                }

                R++;
            }
            result += R - L;

            //L右进一步，判断是否需要有出队操作
            if (minQueue.peekFirst() == L) {
                minQueue.pollFirst();
            }
            if (maxQueue.peekFirst() == L) {
                maxQueue.pollFirst();
            }

        }
        return result;
    }
}
